package dp;

/**
 * @Description 剑指 Offer 60. n个骰子的点数
 * @Author Firenut
 * @Date 2023-03-12 16:25
 */
public class T60_dicesProbability {
    // 解法2：dp
    // 1)定义：dp[i][j] 表示i个骰子点数和为j的情况数
    // 2)递归关系式：
    //   dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6]
    // 3)初始值：dp[1][1]=dp[1][2]=dp[1][3]=...=dp[1][6]=1
    // 4)返回值：
    //   填充到结果数组：dp[n][1]/(6^n)、dp[n][2]/(6^n)、dp[n][3]/(6^n)、dp[n][4]/(6^n)、dp[n][5]/(6^n)、dp[n][6]/(6^n)

    // 性能分析：
    // 时间复杂度: 一共用到3个for循环，但是最后一个for循环的次数是固定最多为6的，是常数级的，所以时间复杂度为O(n^2)
    // 空间复杂度: 需要开辟二维dp数组，结果数组ans，所以空间复杂度为 O(n^2)
    public double[] dicesProbability(int n) {
        int [][]dp = new int[n+1][6*n+1];
        for(int i=1;i<=6;i++){ //填充1个骰子的情况
            dp[1][i]=1;
        }
        for(int i=2;i<=n;i++){
            for(int j=i;j<=6*i;j++){
                for(int k=1;k<=6;k++){
                    // dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6];
                    if(j>=k){  // 防止越界
                        dp[i][j]+=dp[i-1][j-k];
                    }else{
                        break;
                    }
                }
            }
        }
        double [] ans = new double[5*n+1]; // 结果数组,记录的是值从n到6*n的各个点数和的个数(共6n-n+1=5n+1个)
        double sum = Math.pow(6,n);
        int index=0;
        for(int i=n;i<6*n+1;i++){
            ans[index++]=dp[n][i]/sum;
        }
        return ans;
    }

    // 解法1：暴力法
    // 以两个骰子为例,假设点数为x的情况有k种,则其出现的概率为: k/(6^2)  --- 即 k/(6^n)
    // 可以设置一个((2+1) * (2+1))的数组nums[2+1][2+1],然后逐个遍历并将其值记录到一个一维数组中（记录点数和 从2~6*2的情况个数,然后遍历每个元素,去除以6^n得到每种点数和的概率
    // 当然如果是n个骰子就需要构造一个n维数组，显然是很麻烦的，而且时间复杂度是6^n
}
